package com.breeze.sort;

/**
 * 三、插入排序（优化版）
 * 普通版一个元素插入有序表时有可能发生很多交换，从而性能大大折扣。优化版旨在减少交换次数。
 */
public class InsertionSortImprove implements Sort {
    @Override
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int index = i;
            // 建立待插入数的副本
            int temp = arr[index];
            while (index > 0 && temp < arr[index - 1]) {
                // 采用赋值操作，并非交换操作，从而提高性能
                arr[index] = arr[index - 1];
                index--;
            }
            arr[index] = temp;
        }
    }
}
